package leetcode.binaryTree;

import utils.printer.BinaryTrees;
import datastructure.tree.BinarySearchTree;
import datastructure.tree.TreeNode;

/**
 * @Description: https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
 *
 * 草稿(旧)：1
 *
 * @Author Ammar
 * @Create 2023/3/29 23:21
 */
public class _114_二叉树展开为链表 {

    public static void flatten(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) return;
        // 将左子树变为链表
        flatten(root.left);
        // 将右子树变为链表
        flatten(root.right);
        // 将右子树的链表拼接到左子树链表的末尾的右边
        TreeNode left = root.left;
        while (left != null) {
            TreeNode leftRight = left.right;
            if (leftRight == null) {
                left.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            left = leftRight;
        }
    }
    
    public static void main(String[] args) {
        Integer[] data = new Integer[]{
                7, 4, 9, 2, 5, 8 ,11, 3, 12, 1
        };
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            binarySearchTree.add(data[i]);
        }
        BinaryTrees.println(binarySearchTree);
        flatten(binarySearchTree.getRoot());
        BinaryTrees.println(binarySearchTree);
    }
}
